from collections import defaultdict
import math


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) < 3:
            return len(points)
        points.sort()# 根据横坐标排序，横坐标相同再排纵坐标
        ans = 0
        for i in range(len(points) - 1):
            count = defaultdict(int)
            dup = 1  # points[i]自身
            # 遍历每个点与其后边点构成的梯度
            for j in range(i + 1, len(points)):
                if points[j] == points[i]:
                    dup += 1
                    continue
                slp = self.slope(points[i], points[j])
                count[slp] += 1
            ans = max(ans, max(count.values() or [0, ]) + dup)
        return ans

    def slope(self, pa, pb):
        dx = pa[0] - pb[0]
        dy = pa[1] - pb[1]
        if dx == 0:
            return (0, pa[1])
        if dy == 0:
            return (pa[0], 0)
        d = math.gcd(dx, dy)# 返回最大公约数
        return (dx / d, dy / d)# 该方法表示梯度